package com.jn.algorithm.day005.question15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 江南大学1033190417
 * @date 2022/4/19 11:00
 */
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        if (!contains(result, list)) {
                            result.add(list);
                        }
                    }
                }
            }
        }
        return result;
    }

    public boolean contains(List<List<Integer>> now, List<Integer> another) {
        boolean flag = false;
        for (List<Integer> l : now) {
            boolean f = true;
            for (Integer n : l) {
                if (!another.contains(n)) {
                    f = false;
                    break;
                }
            }
            if (f) {
                flag = true;
                break;
            }
        }
        return flag;
    }


    //排序加双指针
    public List<List<Integer>> threeSum2(int[] nums) {
        //排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        for (int first = 0; first < length; first++) {
            //如果和上次枚举的数字一样
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = length - 1;
            int target = -nums[first];
            for (int second = first + 1; second < length; second++) {
                //如果和上次枚举的相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                //如果指针重合，随着后序b的增加，肯定不会有满足的了，直接跳出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    result.add(list);
                }
            }
        }
        return result;
    }


    //自己写一遍
    public List<List<Integer>> threeSum3(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        int length = nums.length;
        for (int first = 0; first < length; first++) {
            //如果上次枚举过了
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = length - 1;
            //往下就是双指针
            for (int second = first + 1; second < length; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[first] + nums[second] + nums[third] > 0) {
                    --third;
                }
                if (nums[first] + nums[second] + nums[third] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    result.add(list);
                }
            }
        }
        return result;
    }

    //排序+双指针另一种写法:貌似不行
    public List<List<Integer>> threeSum4(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int length = nums.length;
        for (int first = 0; first < length; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int second = first + 1;
            int third = length - 1;
            while (second < third) {
                int sum = nums[first] + nums[second] + nums[third];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    result.add(list);
                }
                if (sum < 0) {//移动左指针
                    int k = second + 1;
                    while (k < third && nums[k] == nums[second]) {
                        ++k;
                    }
                    second = k;
                }
                if (sum > 0) {//移动右指针
                    int k = third - 1;
                    while (second < k && nums[k] == nums[third]) {
                        --k;
                    }
                    third = k;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] nums = new int[]{0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0};
        System.out.println(solution.threeSum4(nums));
    }
}
